home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 1 / Cream of the Crop 1.iso / PROGRAM / CTOOLS10.ARJ / AVLTST.C < prev    next >
C/C++ Source or Header  |  1991-12-31  |  3KB  |  132 lines
  1. /* Simple program to test the AVL tree routines */
  2.  
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5. #include <string.h>
  6. #include <time.h>
  7. #include <malloc.h>
  8. #include "debug.h"
  9. #include "avl.h"
  10.  
  11. AVL_TREE    *tree;
  12.  
  13. typedef struct {
  14.     int        key;
  15.     } REC;
  16.  
  17. int my_cmp(REC *r1,REC *r2)
  18. {
  19.     return r1->key - r2->key;
  20. }
  21.  
  22. void my_prnt(FILE* out,REC *r)
  23. {
  24.     fprintf(out, r ? "%3d" : "   ",r->key);
  25. }
  26.  
  27. void my_visit(void *params,REC *r)
  28. {
  29.     printf("%d\n",r->key);
  30. }
  31.  
  32. void docmd(int cmd,int v1,int v2)
  33. {
  34.     REC        *p,*p2;
  35.     REC        r,r2;
  36.  
  37.     switch (cmd) {
  38.         case 'd':
  39.         case 'D':
  40.             r.key = v1;
  41.             if ((p = avl_delete(tree,&r)) == NULL)
  42.                 printf("Node is NOT in tree\n");
  43.             else {
  44.                 printf("Deleted node (%d).\n",p->key);
  45.                 avl_freenode(p);
  46.                 }
  47.             break;
  48.         case 'n':
  49.         case 'N':
  50.             if ((p = avl_delmin(tree)) == NULL)
  51.                 printf("Tree is empty\n");
  52.             else {
  53.                 printf("Removed node (%d).\n",p->key);
  54.                 avl_freenode(p);
  55.                 }
  56.             break;
  57.         case 'm':
  58.         case 'M':
  59.             if ((p = avl_delmax(tree)) == NULL)
  60.                 printf("Tree is empty\n");
  61.             else {
  62.                 printf("Removed node (%d).\n",p->key);
  63.                 avl_freenode(p);
  64.                 }
  65.             break;
  66.         case 'f':
  67.         case 'F':
  68.             r.key = v1;
  69.             if ((p = avl_findsym(tree,&r)) != NULL)
  70.                 printf("Node %d found\n", r.key);
  71.             else
  72.                 printf("Node NOT found\n");
  73.             break;
  74.         case 'r':
  75.         case 'R':
  76.             r.key = v1;    r2.key = v2;
  77.             printf("Range searching [%d,%d]:\n",v1,v2);
  78.             avl_range(tree,&r,&r2,my_visit,NULL);
  79.             break;
  80.         case 'i':
  81.         case 'I':
  82.             if(!(p = avl_newnode(sizeof(REC))))
  83.                 printf("Out of memory\n");
  84.             else {
  85.                 p->key = v1;
  86.                 if ((p2 = avl_insert(tree,p)) != NULL) {
  87.                     fprintf(stderr,"%d is already in the tree\n",p2->key);
  88.                     avl_freenode(p);
  89.                     }
  90.                 }
  91.             break;
  92.         case 'a':
  93.         case 'A':
  94.             avl_empty(tree,avl_freenode);
  95.             break;
  96.         case 'q':
  97.         case 'Q':
  98.             exit(0);
  99.         default:
  100.             printf("Invalid command...\n");
  101.         }
  102.  
  103.     avl_print(stdout,tree,my_prnt,false);
  104.     printf("\n");
  105. }
  106.  
  107. void main(int argc,char *argv[])
  108. {
  109.     char        buf[255];
  110.     int            v1,v2;
  111.  
  112.     tree = avl_init(my_cmp);
  113.     for(++argv; --argc > 0; ++argv) {
  114.         sscanf(*argv+1,"%d,%d",&v1,&v2);
  115.         docmd(**argv,v1,v2);
  116.         }
  117.  
  118.     printf("commands are: iN   - Insert node N into tree\n");
  119.     printf("              dN   - Delete node N\n");
  120.     printf("              m    - Delete maximum valued node\n");
  121.     printf("              n    - Delete minimum valued node\n");
  122.     printf("              fN   - Find node N\n");
  123.     printf("              rL,U - Range search the range [L,U]\n");
  124.     printf("              a    - Delete entire tree\n");
  125.     printf("              q    - Quit (exit)\n");
  126.  
  127.     for(; gets(buf); printf("i/d/m/n/f/r/a/q: ") ) {
  128.         sscanf(buf+1,"%d,%d",&v1,&v2);
  129.         docmd(*buf,v1,v2);
  130.         }
  131. }
  132.